package algorithm;

import java.util.LinkedList;
import java.util.Queue;

public class Leetcode112 {

    /**
     * 广度优先算法
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        Queue<TreeNode> queNode = new LinkedList<>();
        Queue<Integer> queVal = new LinkedList<>();

        queNode.offer(root);
        queVal.offer(root.val);

        while (!queNode.isEmpty()) {
            TreeNode node = queNode.poll();
            int temp = queVal.poll();

            if (node.left == null && node.right == null) {
                if (temp == targetSum) {
                    return true;
                }
                continue;
            }

            if (node.left != null) {
                queNode.offer(node.left);
                queVal.offer(node.left.val + temp);
            }

            if (node.right != null) {
                queNode.offer(node.right);
                queVal.offer(node.right.val + temp);
            }
        }
        return false;
    }



    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        return hasPathSumHelp(root, targetSum);
    }

    public boolean hasPathSumHelp(TreeNode root, int targetSum) {
        if (root.left == null && root.right == null) {
            if (targetSum == 0) {
                return true;
            }
        }

        if (root.left != null) {
            return hasPathSumHelp(root.left, targetSum - root.left.val);
        }

        if (root.right != null) {
            return hasPathSumHelp(root.right, targetSum - root.right.val);
        }

        return false;
    }

}
